package com.sheepone.util.algorithm;

import com.sheepone.util.string.StringUtil;

/**
 * @author Miss.杨
 * @description
 * @since 2024/3/4 - 14:00
 */
public class PrefixAndSuffixUtil {

    /**
     * 查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""
     * time-complexity: O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
     * space-complexity: O(1)。
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return StringUtil.EMPTY_STRING;
        }
        int length = strs.length;
        if (length == 1) {
            return strs[0];
        }
        int len = strs[0].length();
        for (int i = 1; i < length; i++) {
            len = Math.min(len, strs[i].length());
            for (int j = len - 1; j >= 0; j--) {
                if (strs[0].charAt(j) != strs[i].charAt(j)) {
                    if (j == 0) {
                        return StringUtil.EMPTY_STRING;
                    }
                    len = j;
                }
            }
        }
        return strs[0].substring(0, len);
    }

    /**
     * 获取目标字符串的最长公共前后缀长度数组
     * @url: <a href="https://blog.csdn.net/qq_62982856/article/details/128003067">...</a>
     * <p>
     * 如果字符串长度为size，那么其前后缀（长度为len，且顺序都是从左往右）在字符串中的起止索引如下
     * <p>
     * 前缀 （不包括字符串的最后一个字符） ：[ 0 , len - 1]
     * <p>
     * 后缀 （不包括字符串的第一个字符）  ：[ size - len , size - 1 ]
     * @see KmpUtil
     * @param pattern
     * @return
     */
    public static int[] longestCommonPrefixAndSuffixLengthArray(String pattern) {
        int length = pattern.length();
        int[] next = new int[length];

        // 第一个字符既没有前缀也没有后缀，所以最长公共前后缀为0
        next[0] = 0;

        // len有两个作用：
        // 1. 记录当前“匹配成功”的最长公共前后缀长度
        // 2. 记录当前“正在匹配”的最长公共前后缀的起始位置
        int len = 0;

        int i = 1;
        // 从第二个字符开始比较
        while (i < length) {// i ：表面正在计算最长公共前后缀的字串是[0,i]

            // 因为前后缀都是从 左往右 延申 的，
            // 所以当前正在匹配的最长公共前后缀是，pattern[ 0, len - 1 ] + pattern[i]

            if (pattern.charAt(len) == pattern.charAt(i)) { // pattern[ 0 , len ] == pattern[ 0, len - 1 ] + pattern[ i ]
                next[i++] = ++len;
            } else {
                if (len == 0) {
                    // 没有最长公共前后缀累积
                    next[i++] = len;
                } else {
                    // 有最长公共前后缀累积

                    // 正是因为 next[len - 1]存储的是 pattern[0, len - 1]的最长公共前后缀 的长度
                    // 所以 pattern[0,next[len- 1]] 是 pattern[0, len - 1] 的最长公共前后缀

                    // 而当前 匹配失败的是 pattern[ 0 , len ] 与 pattern[ 0, len - 1 ] + pattern[ i ]
                    // 那么为了高效，我们就得找的到 pattern[0, len - 1] 的最长公共前后缀
                    // 因为该最长公共前后缀的后缀也是 pattern[0, len - 1] 的后缀（这里便是发挥“后缀”的作用了）
                    len = next[len - 1];
                }
            }
        }
        return next;
    }
}
